//给你一个整数数组 nums 和一个整数 k 。 
//
// 一个元素 x 在数组中的 频率 指的是它在数组中的出现次数。 
//
// 如果一个数组中所有元素的频率都 小于等于 k ，那么我们称这个数组是 好 数组。 
//
// 请你返回 nums 中 最长好 子数组的长度。 
//
// 子数组 指的是一个数组中一段连续非空的元素序列。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [1,2,3,1,2,3,1,2], k = 2
//输出：6
//解释：最长好子数组是 [1,2,3,1,2,3] ，值 1 ，2 和 3 在子数组中的频率都没有超过 k = 2 。[2,3,1,2,3,1] 和 [3,1
//,2,3,1,2] 也是好子数组。
//最长好子数组的长度为 6 。
// 
//
// 示例 2： 
//
// 
//输入：nums = [1,2,1,2,1,2,1,2], k = 1
//输出：2
//解释：最长好子数组是 [1,2] ，值 1 和 2 在子数组中的频率都没有超过 k = 1 。[2,1] 也是好子数组。
//最长好子数组的长度为 2 。
// 
//
// 示例 3： 
//
// 
//输入：nums = [5,5,5,5,5,5,5], k = 4
//输出：4
//解释：最长好子数组是 [5,5,5,5] ，值 5 在子数组中的频率没有超过 k = 4 。
//最长好子数组的长度为 4 。
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 10⁵ 
// 1 <= nums[i] <= 10⁹ 
// 1 <= k <= nums.length 
// 
//
// Related Topics 数组 哈希表 滑动窗口 👍 27 👎 0

package leetcode.editor.cn;

import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;

//java:最多 K 个重复元素的最长子数组
public class Q2958LengthOfLongestSubarrayWithAtMostKFrequency {
    public static void main(String[] args){
        Solution solution = new Q2958LengthOfLongestSubarrayWithAtMostKFrequency().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int maxSubarrayLength(int[] nums, int k) {
        int n = nums.length, left = 0, res = 0;
        Map<Integer, Integer> map = new HashMap<>();
        for (int right = 0; right < n; right++) {
            map.put(nums[right], map.getOrDefault(nums[right], 0) + 1);
            // 不需要计算最大，只需要判定map.get(nums[right]，前面的一定是没问题的
//            int maxCount = map.values().stream().max(Integer::compareTo).orElse(0);
            while (map.get(nums[right]) > k) {
                map.put(nums[left], map.get(nums[left]) - 1);
//                maxCount = map.values().stream().max(Integer::compareTo).orElse(0);
                left++;
            }
            res = Math.max(res, right - left + 1);
        }
        return res;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}